
// 几何线段

// 判断点是不是在线段上
// 通过判断斜率来判断 ，但考虑点的计算是浮点型，需要设定一个阈值
// 判断三点是否共线 
export const onSegment = (p1, p2, q) => {
    let k1 = ((p2[1] - p1[1]) / (p2[1] - p1[1])).toFixed(3)
    let k2 = ((q[1] - p1[1]) / (q[1] - p1[1])).toFixed(3)
    let error = Math.abs(k2 - k1)
    if (error - 0.1 <= Number.EPSILON) {
        return [p1, p2]
    } else {
        return null
    }
}


export const pointInSegments = (p, segments) => {
    for (let i = 1; i < segments.length; i++) {
        let pi = segments[i - 1]
        let pj = segments[i]
        if (onSegment(pi, pj, p)) {
            return [pi, pj]
        }
    }
    return null
}

// 判断点是在线段的左边还是右边
// 比如判断是凹多边形还是凸多边形；判断点是凹点还是凸点；判断线段是否相交；判断两点是否在线段两侧
// 顺时针方向 三点组成的向量的叉积z值为负，逆时针方向三点组成的向量的叉积z值为正。





// 求线段交点
// 算法一: 求两条线段所在直线的交点, 再判断交点是否在两条线段上.
export const segmentsIntr = (a, b, c, d) => {

    /** 1 解线性方程组, 求线段交点. **/
    // 如果分母为0 则平行或共线, 不相交 
    var denominator = (b[1] - a[1]) * (d[0] - c[0]) - (a[0] - b[0]) * (c[1] - d[1]);
    if (denominator == 0) {
        return false;
    }

    // 线段所在直线的交点坐标 (x , y) 
    var x = ((b[0] - a[0]) * (d[0] - c[0]) * (c[1] - a[1])
        + (b[1] - a[1]) * (d[0] - c[0]) * a[0]
        - (d[1] - c[1]) * (b[0] - a[0]) * c[0]) / denominator;
    var y = -((b[1] - a[1]) * (d[1] - c[1]) * (c[0] - a[0])
        + (b[0] - a[0]) * (d[1] - c[1]) * a[1]
        - (d[0] - c[0]) * (b[1] - a[1]) * c[1]) / denominator;

    /** 2 判断交点是否在两条线段上 **/
    if (
        // 交点在线段1上 
        (x - a[0]) * (x - b[0]) <= 0 && (y - a[1]) * (y - b[1]) <= 0
        // 且交点也在线段2上 
        && (x - c[0]) * (x - d[0]) <= 0 && (y - c[1]) * (y - d[1]) <= 0
    ) {

        // 返回交点p 
        return {
            x: x,
            y: y
        }
    }
    //否则不相交 
    return false

}

// 算法二: 判断每一条线段的两个端点是否都在另一条线段的两侧, 是则求出两条线段所在直线的交点, 否则不相交.
export const segmentsIntr2 = (a, b, c, d) => {

    //线段ab的法线N1 
    var nx1 = (b[1] - a[1]), ny1 = (a[0] - b[0]);

    //线段cd的法线N2 
    var nx2 = (d[1] - c[1]), ny2 = (c[0] - d[0]);

    //两条法线做叉乘, 如果结果为0, 说明线段ab和线段cd平行或共线,不相交 
    var denominator = nx1 * ny2 - ny1 * nx2;
    if (denominator == 0) {
        return false;
    }

    //在法线N2上的投影 
    var distC_N2 = nx2 * c[0] + ny2 * c[1];
    var distA_N2 = nx2 * a[0] + ny2 * a[1] - distC_N2;
    var distB_N2 = nx2 * b[0] + ny2 * b[1] - distC_N2;

    // 点a投影和点b投影在点c投影同侧 (对点在线段上的情况,本例当作不相交处理); 
    if (distA_N2 * distB_N2 >= 0) {
        return false;
    }

    // 
    //判断点c点d 和线段ab的关系, 原理同上 
    // 
    //在法线N1上的投影 
    var distA_N1 = nx1 * a[0] + ny1 * a[1];
    var distC_N1 = nx1 * c[0] + ny1 * c[1] - distA_N1;
    var distD_N1 = nx1 * d[0] + ny1 * d[1] - distA_N1;
    if (distC_N1 * distD_N1 >= 0) {
        return false;
    }

    //计算交点坐标 
    var fraction = distA_N2 / denominator;
    var dx = fraction * ny1,
        dy = -fraction * nx1;
    return { x: a[0] + dx, y: a[1] + dy };
}

//    算法三: 判断每一条线段的两个端点是否都在另一条线段的两侧, 是则求出两条线段所在直线的交点, 否则不相交.
// 不通过法线投影来判断点和线段的位置关系, 而是通过点和线段构成的三角形面积来判断.
// 如果”线段ab和点c构成的三角形面积”与”线段ab和点d构成的三角形面积” 构成的三角形面积的正负符号相异,
// 那么点c和点d位于线段ab两侧.
export function segmentsIntr3(a, b, c, d) {

    // 三角形abc 面积的2倍 
    var area_abc = (a[0] - c[0]) * (b[1] - c[1]) - (a[1] - c[1]) * (b[0] - c[0]);

    // 三角形abd 面积的2倍 
    var area_abd = (a[0] - d[0]) * (b[1] - d[1]) - (a[1] - d[1]) * (b[0] - d[0]);

    // 面积符号相同则两点在线段同侧,不相交 (对点在线段上的情况,本例当作不相交处理); 
    if (area_abc * area_abd >= 0) {
        return false;
    }

    // 三角形cda 面积的2倍 
    var area_cda = (c[0] - a[0]) * (d[1] - a[1]) - (c[1] - a[1]) * (d[0] - a[0]);
    // 三角形cdb 面积的2倍 
    // 注意: 这里有一个小优化.不需要再用公式计算面积,而是通过已知的三个面积加减得出. 
    var area_cdb = area_cda + area_abc - area_abd;
    if (area_cda * area_cdb >= 0) {
        return false;
    }

    //计算交点坐标 
    var t = area_cda / (area_abd - area_abc);
    var dx = t * (b[0] - a[0]),
        dy = t * (b[1] - a[1]);
    return { x: a[0] + dx, y: a[1] + dy };

}

